/**
 * 面试题43：1～n 整数中 1 出现的次数
 */
public class Offer_43 {
    /**
     * 枚举每一数位上 1 的个数
     * <p>
     * 将 1 ~ n 的个位、十位、百位、...的 1 出现次数相加，即为 1 出现的总次数
     * <p>
     * 时间复杂度：O(logn)
     * <p>
     * 空间复杂度：O(1)
     */
    public int countDigitOne(int n) {
        int ans = 0;
        // 位因子，1表示个位，10表示十位，。。。
        int digit = 1;
        // cur 表示当前位，high 表示比当前位高的位，low 表示比当前位低的位
        int high = n / 10, cur = n % 10, low = 0;
        // 当 high 和 cur 同时为 0 时，说明已经越过最高位，结束循环
        while (high != 0 || cur != 0) {
            if (cur == 0) {
                // 当前位数字为 0，此位 1 的出现次数只由高位 high 决定
                // 计算式：high * dight
                ans += high * digit;
            } else if (cur == 1) {
                // 当前位数字为 1，此位 1 的出现次数由高位 high 和低位 low 决定
                // 计算式：high * dight + (low + 1)
                ans += (high * digit) + (low + 1);
            } else {
                // 当前位数字大于 1，此位 1 的出现次数只由高位 high 决定
                // 计算式：(high + 1) * digit
                ans += (high + 1) * digit;
            }
            // 计算下一轮的
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return ans;
    }
}
